Problem solvers which use constraint programming techniques to provide solutions to planning, scheduling and configuration problems are known and are currently commercially available. For example, the constraint programming engines provided by Ilog, Inc. These types of problem solvers are used to help organizations make better plans and schedules. For example, to plan production at a manufacturing plant, plan workforce schedules, plan truck loading, set routes for delivering goods or services, deciding when to release seats or hotel nights at a lower price, determining a optimal number of trades to bring a stock index fund back into compliance and many other applications.
Constraint programming techniques involve stating relations between variables in the form of constraints. A problem may be stated as a number of unknown variables comprising a state of the world. The problem solver searches for possible solutions to the problem by searching for values for all the variables. A large number of constraints are specified (for example, there may be tens of thousands of constraints over thousands of variables). The constraints are embedded in a host programming language of any suitable type. For example, a logic programming language such as Prolog or by using a separate library in conjunction with an imperative programming language such as C++ or Java (trade mark). The hog solver (trade mark) mentioned above is an example of such a C++ library for constraint programming.
One of the characteristics of such problem solvers is a high runtime variance. That is, the time taken to solve a given problem instance is difficult to predict (even for different problems of the same size, or for different instances drawn from the same distribution of instances of a problem type). This is a problem in many applications where it is necessary to ensure that a solution is found before reaching a specified time limit.
Previously this problem has been addressed by carrying out extensive tuning or trials of the problem solver on known training data to select a set of control parameters to be used in the problem solver. However, this is time consuming, complex and may result in relatively poor performance. The selected control parameters are a compromise between many possible choices and if the training data is not representative the selected parameters may not be appropriate when new, previously unseen data is presented to the problem solver.
It is required to provide improved automated methods and apparatus for selecting such control parameters.